#include <stdio.h>
#include <stdlib.h>

int MaxNum=1000000; //边权最大值
int n; //节点数目
int *dist;
int *state;
double **data;
//查找权值最小的节点
int findMinNode()
{
	int minNode = -1, min = MaxNum;
	int i;
	for(i = 0; i < n; i++)
		if ((dist[i] < min) && (!state[i]))
		{
			min = dist[i];
			minNode = i;
		}
		return minNode;
}

int main()
{
	FILE *fr,*fw;
	fr = fopen("Dijkstra.in","r");
	fw = fopen("Dijkstra.out","w");
	fscanf(fr,"%d",&n);
	int i,j;
	int startNode;
	dist = malloc(sizeof(int)*n);
	state = malloc(sizeof(int)*n);
	data = malloc(sizeof(double*)*n);
	for(i = 0;i < n;i++)
	{
		dist[i] = 0;
		state[i] = 0;
		data[i] = malloc(sizeof(double)*n);
	}

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			fscanf(fr,"%lf",&data[i][j]);
			if (data[i][j] == 0) data[i][j] = MaxNum;
		}
	fscanf(fr,"%d",&startNode);
	startNode -= 1;

	for(i = 0; i < n; i++)
		dist[i]=data[startNode][i];
	state[startNode] = 1;
	int done = 1;
	while(done < n)
	{
		int node = findMinNode();
		if(node != -1)
		{
			done++; //找到的点的数目加1
			state[node] = 1; //标记已经找到了从节点1到节点node的最短路径
			for(i = 0; i < n; i++)//更新还没有找到的点的路径值
				if ((dist[i] > dist[node] + data[node][i]) && (!state[i]))
					dist[i] = dist[node] + data[node][i];
		}
		else break;
	}
	for(i = 0;i < n;i++)
	{
		if(i != startNode)
		{
			fprintf(fw,"%d ",dist[i]);
		}
	}
	fprintf(fw,"\n");
	return 0;
}
